package LeetCode;

public class TrapingRainWater
{

  //pass both
  //can solve the google interview problem as well
  public int trap(int[] A)
  {
    // Start typing your Java solution below
    // DO NOT write main() function

    int n = A.length;
    int i = 0, j = n - 1, sum = 0;

    while (i < j) {
      //get the first one that is 
      //larger than the right one from the left
      while (i < j && A[i] < A[i + 1]) {
        //google interview
        //sum+=A[i]
        i++;
      }
      //get the first one that is 
      //larger than the left on the right
      while (i < j && A[j] < A[j - 1]) {
        j--;
      }

      if (i == j) {
        break;
      }

      if (A[i] > A[j]) {
        int k = j - 1;//which is smaller than A[j]
        for ( ; k > i ; k--) {
          if (A[k] < A[j]) {
            //google interview
            //sum+=A[j]
            sum += A[j] - A[k];
          }
          else {
            break;
          }
        }
        //now A[k] is greater than A[j]
        j = k;
      }

      else {
        int k = i + 1;//which is smaller than A[i]
        //till we find the k that
        //A[k]>=A[i]
        for ( ; k < j ; k++) {
          if (A[k] < A[i]) {
            sum += A[i] - A[k];
          }
          else {
            break;
          }
        }

        i = k;
      }
    }

    return sum;
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub
    TrapingRainWater t = new TrapingRainWater();
    System.out.println(t.trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
  }

}
